//211.添加与搜索单词-数据结构设计
//https://leetcode.cn/problems/design-add-and-search-words-data-structure
class WordDictionary {
    WordDictionary* next;
    WordDictionary* arr[26];
    bool isEnd;
public:
    WordDictionary():next(nullptr),isEnd(false) {
        memset(arr, 0, sizeof(arr));
    }
    
    void addWord(string word) {
        WordDictionary* nd = this;
        for(char& c:word)
        {
            if(nd->arr[c - 'a'] == nullptr) nd->arr[c-'a'] = new WordDictionary;
            nd = nd->arr[c-'a'];
        }
        nd->isEnd = true;
    }
    
    bool search(string word) {
        return dfs(word,0,this);
    }
private:
    bool dfs(string& s,int i,WordDictionary* w)
    {
        if(i == s.size()) return w->isEnd;
        //如果字母已经明确 则查找表
        if(s[i]>='a' && s[i] <= 'z')
        {
            if(w->arr[s[i]-'a'] && dfs(s,i+1,w->arr[s[i]-'a'])) return true;
        }
        else //否则遍历整个表 直到找到一条能够符合要求的单词为止
        {
            for(int k = 0;k<26;++k)
                if(w->arr[k] && dfs(s, i + 1, w->arr[k])) return true;
        }
        return false;
    }
};